package DataStructure.linkList;

import utils.CommonUtils;

/**
 * 206. 反转链表 https://leetcode.cn/problems/reverse-linked-list
 * 题目简述：给你单链表的头节点head，请你反转链表，并返回反转后的链表。
 */
public class ReverseList {

    public static void main(String[] args) {
        new ReverseList().reverseList(CommonUtils.makeNodeList(new int[]{1,2,3,4,5}));
    }

    /**
     * 思路一：初始时前指针pre指向null，后指针cur指向head，然后进行遍历，遍历过程中反转cur的指向使其指向pre，
     * 然后将pre和cur向右移动一格，当cur指向null时，pre必已指向最后一个节点，即为新的头结点 返回。
     */
    public ListNode reverseList(ListNode head) {
        ListNode pre = null, cur = head;//重点
        while(cur != null) {
            ListNode t = cur.next;
            cur.next = pre;
            pre = cur;
            cur = t;
        }
        //当cur指向null时，pre必已指向最后一个节点
        return pre;
    }

    /**
     * 思路二：递归。反转链表head 等于 反转链表head.next 并 反转节点head与head.next的指向，递归终止:当递归到尾结点时终止 返回尾结点，即为反转链表后的头结点，逐层向上返回这个节点。
     * 参考：https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/solutions/476929/jian-zhi-offer-24-fan-zhuan-lian-biao-die-dai-di-2/ 评论1
     */
    public ListNode reverseList2(ListNode head) {
        if(head == null || head.next == null) {
            return head;//当递归到尾结点时终止 返回尾结点
        }
        ListNode newHead = reverseList(head.next);//反转链表head.next，并返回反转后的头结点
        head.next.next = head;
        head.next = null;
        return newHead;//链表head和链表head.next它俩反转后的头节点是同一个
    }
}
